This invention relates generally to methods of timing recovery, and in particular to a digital phase locked loop that uses a recursive, weighted least squares algorithm to determine maximum likelihood estimates of the period and phase of an incoming signal.
Phase locked loops are used to synchronize an electronic device to a regular electrical signal. One possible form that a source signal sideal can take is sinusoidal,
sideal(xcfx89,xcfx86,t)=sin(xcfx89t+xcfx86).
If the source signal has an unknown frequency xcfx89s, an unknown phase xcfx86s, and is corrupted by noise n(t), the phase locked loop receives an input signal s(t), where
s(t)=sideal(xcfx89s,xcfx86s,t)+n(t).
The phase locked loop estimates the values of the frequency and the phase of the received signal to be {circumflex over (xcfx89)} and {circumflex over (xcfx86)}, respectively. Synchronization occurs when the difference between the estimates and the true values have decreased below given tolerances xcex5xcfx89and xcex5xcfx86:
xe2x80x83|xcfx89sxe2x88x92{circumflex over (xcfx89)}| less than xcex5xcfx89 and |xcfx86sxe2x88x92{circumflex over (xcfx86)}| less than xcex5xcfx86.
The phase locked loop uses the estimates {circumflex over (xcfx89)} and {circumflex over (xcfx86)} to generate an output signal. Phase locked loops typically achieve synchronization between the input and output signals using a feedback loop comprising a phase detector, a low pass filter, and a voltage controlled oscillator. While the feedback loop converges to the true values of the frequency and phase given infinite time, the rate of convergence is often slow.
A number of phase locked loops have been designed to have an improved convergence rate. In U.S. Pat. No. 5,754,598 by Barrett, Jr. et al., modern optimal control techniques are used to control a phase locked loop for a predetermined period. Classical control techniques are used after the predetermined period. In U.S. Pat. No. 5,291,144 by Ichiyoshi, the input and output signals are complex. The output signal is multiplied by the input signal to obtain a complex phase difference, which is used as feedback to control the output signal.
U.S. Pat. No. 5,093,847 by Cheng describes an adaptive phase locked loop that has coefficients that are automatically adjusted to minimize an error signal. A purely digital approach is presented in xe2x80x9cEfficient Digital Techniques for Implementing a Class of Fast Phase-Locked Loopsxe2x80x9d by Kobayashi et al., IEEE Transactions on Industrial Electronics, 43 (1996) pp. 616-620. In this approach, several previous measurements of the frequency of the input signal are averaged to calculate the estimated frequency {circumflex over (xcfx89)}. However, none of the above phase locked loops are stable under large perturbations of the input signal. Furthermore, the digital approach mentioned above fails to take full advantage of modern computing power.
Finally, in U.S. Pat. No. 5,875,215 by Dobrica, a carrier synchronizing unit uses a recursive least square type phase and amplitude estimation. The synchronizing unit uses known symbol information to characterize the channel through which the input signal propagates prior to being received. However, the synchronizing unit does not lock onto the input signal directly, nor does it estimate the period of the input signal.
Furthermore, many current phase locked loops assume that the input signal is periodic. If the input signal is a digital bit stream, however, the signal is not periodic. The potential for a transition between bits occurs regularly, but a transition does not necessarily take place at every potential transition time. Present state-of-the-art systems that lock on to such aperiodic signals are not tolerant to high levels of interference and noise on the input signal.
It is therefore a primary object of the present invention to provide a phase locked loop that converges quickly to an input signal, is robust to perturbations of the input signal, and estimates the period and phase of the input signal using purely digital means. It is an other object of the present invention to provide a phase locked loop that can lock onto a signal having periodic characteristics but which is not itself periodic.
The invention has the advantage that it provides an efficient and stable phase locked loop that can be implemented using modern integrated circuit technology. The invention has the additional advantage that it can lock onto certain noisy aperiodic signals.
A method of estimating a period and a time delay of an input signal comprises the step of identifying a plurality of transition times {tilde over (t)}i of the input signal, where i=xe2x88x92(Nxe2x88x922) to 0. Each transition time {tilde over (t)}i has a corresponding weight xcex1xe2x88x92i{tilde over (xcex3)}i comprising a forgetting factor a and a weighting factor {tilde over (xcex3)}i. The forgetting factor xcex1 reduces the importance of transition times that occurred in the past. The weighting factor {tilde over (xcex3)}i gives the relative importance of transition time {tilde over (t)}i.
Upon receiving an Nth transition time t0 and an Nth weighting factor xcex30, the period and the time delay of the input signal are estimated as {circumflex over (T)} and {circumflex over (t)}xcfx86, respectively. The time delay is proportional to the phase of the input signal. The values of {circumflex over (T)} and {circumflex over (t)}xcfx86 are computed by maximum likelihood techniques using a least squares minimization of an error function that uses the weights xcex1xe2x88x92i{tilde over (xcex3)}i. The estimates are made in a recursive manner, with {circumflex over (T)} depending on xcex1, xcex30, t0, and a preceding maximum likelihood estimate {tilde over (T)} of the period. The value of {circumflex over (t)}xcfx86 depends on xcex1, xcex30, and t0.
The estimates {circumflex over (T)}and {circumflex over (t)}xcfx86 also depend on sums       S          N      -      1              (      n      )        =            ∑              i        =                  -                      (                          N              -              2                        )                              0        ⁢                  i        n            ⁢              a                  -          i                    ⁢                        γ          ~                i            
for n=0, 1, and 2. Specifically,             T      ^        =                  T        ~            +                                                  (                                                S                                      N                    -                    1                                                        (                    0                    )                                                  -                                  S                                      N                    -                    1                                                        (                    1                    )                                                              )                        ⁢                          γ              0                                                          a              ⁡                              (                                                                            S                                              N                        -                        1                                                                    (                        0                        )                                                              ⁢                                          S                                              N                        -                        1                                                                    (                        2                        )                                                                              -                                                            (                                              S                                                  N                          -                          1                                                                          (                          1                          )                                                                    )                                        2                                                  )                                      +                                          (                                                      S                                          N                      -                      1                                                              (                      2                      )                                                        -                                      2                    ⁢                                          S                                              N                        -                        1                                                                    (                        1                        )                                                                              +                                      S                                          N                      -                      1                                                              (                      0                      )                                                                      )                            ⁢                              γ                0                                                    ⁢                  t          0                ⁢                  xe2x80x83                ⁢                  and                                        t        ^            φ        =                                        -                          (                                                S                                      N                    -                    1                                                        (                    2                    )                                                  -                                  2                  ⁢                                      S                                          N                      -                      1                                                              (                      1                      )                                                                      +                                  S                                      N                    -                    1                                                        (                    0                    )                                                              )                                ⁢                      γ            0                                                a            ⁡                          (                                                                    S                                          N                      -                      1                                                              (                      0                      )                                                        ⁢                                      S                                          N                      -                      1                                                              (                      2                      )                                                                      -                                                      (                                          S                                              N                        -                        1                                                                    (                        1                        )                                                              )                                    2                                            )                                +                                    (                                                S                                      N                    -                    1                                                        (                    2                    )                                                  -                                  2                  ⁢                                      S                                          N                      -                      1                                                              (                      1                      )                                                                      +                                  S                                      N                    -                    1                                                        (                    0                    )                                                              )                        ⁢                          γ              0                                          ⁢                        t          0                .            
Once {circumflex over (T)} and {circumflex over (t)}xcfx86 are obtained, the sums are updated in preparation for a subsequent estimate of the period and time delay.
The present method is preferably implemented by an integrated circuit that produces an output signal whose period and time delay are equal to {circumflex over (T)} and {circumflex over (t)}xcfx86, respectively. The physical implementation of the present method therefore results in a digital phase locked loop.
In some embodiments, the forgetting factor xcex1=1. In some embodiments, the weighting factors xcex3i=1. In the preferred embodiment, xcex1 less than 1, and each of the weighting factors xcex3i is given a value indicating a confidence level in the accuracy of transition time ti. The weighting factors are particularly useful when receiving a signal with absent transitions. A weighting factor of zero is assigned to missed transitions; therefore good estimates of the period and time delay are maintained. Thus the digital phase locked loop of the present invention can lock onto some aperiodic signals.
The forgetting factor xcex1 is adjusted to give a desired insensitivity to noise. As xcex1 approaches 1, the estimates {circumflex over (T)} and {circumflex over (t)}xcfx86 of the period and time delay become increasingly unresponsive to noise as well as to long-term changes in the period and time delay of the input signal. The forgetting factor xcex1 is selected so that, after a predetermined number of transition times, the estimates {circumflex over (T)} and {circumflex over (t)}xcfx86 have a desired variance. The digital phase locked loop can therefore be used even when the input signal is very noisy.